#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const int INF=0x3f3f3f3f;
int main() {

	int n,m;
	cin>>n>>m;
	vector<vector<int>> dis(n,vector<int>(n,INF));
	for(int i=0;i<m;++i){
		int x,y,z;
		cin>>x>>y>>z;
		--x,--y;
		dis[x][y]=dis[y][x]=min(dis[x][y],z);
	}
	vector<int> p(n);
	int upper=pow(3,n);
	p[0]=1;
	for(int i=1;i<n;++i){
		p[i]=p[i-1]*3;
	}

	vector<vector<int>> dp(upper,vector<int>(n,INF));
	for(int i=0;i<n;++i){
		dp[p[i]][i]=0;
	}	
	for(int mask=1;mask<upper;++mask){
		for(int i=0;i<n;++i){
			if(dp[mask][i]==INF){
				continue;
			}
			for(int j=0;j<n;++j){
				if(dis[i][j]==INF){
					continue;
				}
				if((mask/p[j])%3<2){
					int next_mask=mask+p[j];
					dp[next_mask][j]=min(dp[next_mask][j],dp[mask][i]+dis[i][j]);
				}
			}
		}
	}
	int nRet=INF;
	for(int mask=1;mask<upper;++mask){
		bool flg=true;
		for(int i=0;i<n;++i){
			if((mask/p[i])%3==0){
				flg=false;
				break;
			}
		}
		
		if(flg){
			for(int i=0;i<n;++i){
				nRet=min(nRet,dp[mask][i]);
			}		
		}
	}
	cout<<(nRet==INF?-1:nRet)<<endl;
	
	return 0;
}
